/* huffman树的构造方法*/

#include<stdlib.h>
#include<stdio.h>

// tree: [56[24[11][13]][32[15][17[7][10[5][5[2][3]]]]]
// generator: http://mshang.ca/syntree/

#define  MAXINT    2147483647
#define  MAXNUM   50    /* 数组w中最多容纳的元素个数，注意 m<=MAXNUM */
#define  MAXNODE  100    /* 哈夫曼树中的最大结点数，注意 2*m-1<MAXNODE */

struct HtNode {        /* 哈夫曼树结点的结构 */
    int ww;
    int parent, llink, rlink;
};

struct HtTree {
    int root;/* 哈夫曼树根在数组中的下标*/
    struct HtNode ht[MAXNODE];
};

typedef struct HtTree *PHtTree; /* 哈夫曼树类型的指针类型 */

/* 构造具有m个叶结点的哈夫曼树*/
PHtTree huffman(int m, int *w) {
    PHtTree pht;
    int i, j, x1, x2, m1, m2;
    pht = (PHtTree) malloc(sizeof(struct HtTree));  /* 创建空哈夫曼树 */
    if (pht == NULL) {
        printf("Out of space!! \n");
        return pht;
    }
    for (i = 0; i < 2 * m - 1; i++) {/* 置初态 */
        pht->ht[i].llink = -1;
        pht->ht[i].rlink = -1;
        pht->ht[i].parent = -1;
        if (i < m)
            pht->ht[i].ww = w[i];
        else
            pht->ht[i].ww = -1;
    }
    for (i = 0; i < m - 1; i++) {/* 每循环一次构造一个内部结点 */
        m1 = MAXINT;
        m2 = MAXINT;/* 相关变量赋初值 */
        x1 = -1;
        x2 = -1;
        for (j = 0; j < m + i; j++)        /* 找两个最小权的无父结点的结点 */
            if (pht->ht[j].ww < m1 && pht->ht[j].parent == -1) {
                m2 = m1;
                x2 = x1;
                m1 = pht->ht[j].ww;
                x1 = j;
            } else if (pht->ht[j].ww < m2 && pht->ht[j].parent == -1) {
                m2 = pht->ht[j].ww;
                x2 = j;
            }

        pht->ht[x1].parent = m + i;    /* 构造一个内部结点 */
        pht->ht[x2].parent = m + i;
        pht->ht[m + i].ww = m1 + m2;
        pht->ht[m + i].llink = x1;
        pht->ht[m + i].rlink = x2;
        pht->root = m + i;
    }
    return pht;
}

int main() {
    int m = 0, j = 0, i = 0, parent = 0;
    int *w;
    PHtTree pht;
    printf("please input m = ");/*输入外部结点个数*/
    scanf("%d", &m);
    if (m < 1) {
        printf("m is not reasonable!\n");
        return 1;
    }
    w = (int *) malloc(sizeof(int) * m);
    if (w == NULL) {
        printf("overflow!\n");
        return 1;
    }
    printf("please input the %d numbers：\n", m);/*输入权值*/
    for (j = 0; j < m; j++)
        scanf("%d", w + j);
    pht = huffman(m, w);
    for (j = 0; j < m; j++) {
        printf("the Reverse code of the %d node is:", j + 1);/*得到的编码应倒过来*/
        i = j;
        while (pht->ht[i].parent != -1) {
            parent = pht->ht[i].parent;
            if (pht->ht[parent].llink == i)
                printf("0");
            else
                printf("1");
            i = parent;
        }
        printf("\n");
    }
    return 0;
}


